#pragma once
#include "RedBlackNode.h"
/**红黑树抽象类*/
class RedBlackAbstruct
{
private:
	RedBlackNode* root;

	RedBlackNode& operator = (const RedBlackNode &);

	RedBlackAbstruct(RedBlackAbstruct &);
protected:
	RedBlackNode* createNode(int key, int value) const;

	/// <summary>
	/// 获取祖父节点
	/// </summary>
	/// <param name="node"></param>
	/// <returns></returns>
	RedBlackNode* getGrandfather(RedBlackNode* node);

	/// <summary>
	/// 获取叔叔节点
	/// </summary>
	/// <param name="node"></param>
	/// <returns></returns>
	RedBlackNode* getUncle(RedBlackNode* node);

	/// <summary>
	/// 获取兄弟节点
	/// </summary>
	/// <param name="node"></param>
	/// <returns></returns>
	RedBlackNode* siblings(RedBlackNode* node);

	// 根节点变颜色条件
	void insetCaseOne(RedBlackNode* node);

	/// <summary>
	/// 其他根节点 变色条件
	/// </summary>
	/// <param name="node"></param>
	void insetCaseTwo(RedBlackNode* node);

	/// <summary>
	/// 插入第二层
	///	<pre>	   
	///			6B 
	///		  /    \
	///		 4R     7R
	///     /  \   /  \
	///    2R  NB NB  NB
	/// 
	///   不满足第红色节点的子节点必须是黑色
	/// </pre>
	/// 
	/// 		6B 
	///		  /    \
	///		 4B     7B
	///     /  \   /  \
	///    2R  NB NB  NB
	///  
	/// 
	/// </summary>
	/// <param name="node"></param>
	void insertCaseThree(RedBlackNode* node);

	/// <summary>
	/// a == a->parent->left && grandfather(a)->right == n->parent
	/// 		6B 
	///			   \
	///			   9R
	///			  /
	///			 7R
	///  右旋
	/// 			
	///			6B
	///			   \
	///				7R
	///				 \
	///				  9R
	/// 	左旋
	///			7B
	///		  /    \
	///		 6R	    9R
	///  
	/// </summary>	
	/// <param name="node"></param>
	void insertCaseFoure(RedBlackNode* node);

	/// <summary>
	///			6B 
	///		  /    \
	///		 3B     9B
	///     /  \
	///    2R  5R
	///		右旋：左子树；当前节点的父节点是红色且叔叔节点是黑色时
	///			3B
	///		  /    \
	///		 2R     6R
	///			  /    \
	///			 5B     9B
	/// </summary>
	/// <param name="node"></param>
	void insertCaseFive(RedBlackNode* node);
	
	/// <summary>
	/// 获取节点颜色
	/// </summary>
	/// <param name="node"></param>
	/// <returns></returns>
	Color getNodeColor(RedBlackNode* node) const;

	/// <summary>
	/// 右旋
	/// </summary>
	/// <param name="node"></param>
	void rotateRight(RedBlackNode* node);

	/// <summary>
	/// 左旋
	/// </summary>
	/// <param name="node"></param>
	void rotateLeft(RedBlackNode* node);

	/// <summary>
	/// 替换节点
	/// </summary>
	/// <param name="old"></param>
	/// <param name="newNode"></param>
	void replaceNode(RedBlackNode* old, RedBlackNode* newNode);

	/// <summary>
	/// 寻找节点的最低的右节点
	/// 进行节点删除时一般时找当前节点的右节点在当当前节点,保证二叉树的特性
	/// </summary>
	RedBlackNode* findTheLowestRightNode(RedBlackNode* node);
	
	/// <summary>
	/// 节点父节点为空 
	/// </summary>
	/// <param name="node"></param>
	void deleteCaseOne(RedBlackNode* node);

	/// <summary>
	/// 节点的兄弟节点是红色，
    ///					  9B
	///				  /	       \
	///		        6B	       15B
	///			   /   \	 /     \
	///			  3B   8B   11R    18B
	///		     /  \      /  \ 
	///		    1R    4R  10B 14B
	///				      /
	///				     9R
	/// 删除18的时候 节点是黑色且没有子节点 双空
	/// </summary>
	/// <param name="node"></param>
	void deleteCaseTwo(RedBlackNode* node);

	/// <summary>
	/// 				  8B
	///				 /	        \
	///		        4R	        12R
	///			  /    \	  /     \
	///			 2B    6B    10B    16B
	///		    /  \  /  \  /  \   /   \
	///		   1B  3B 5B 7B 9B 11B 14B 18B
	/// 删除 7时	【x的兄弟w是黑色的，且w的俩个孩子都是黑色的】
	/// </summary>
	/// <param name="node"></param>
	void deleteCaseThree(RedBlackNode* node);

	/// <summary>
	/// 节点的父节点是红色，且兄弟节点也是黑色且兄弟节点的左右节点是红色
	/// </summary>
	/// <param name="node"></param>
	void deleteCaseFour(RedBlackNode* node);


	///			9B 
	///		  /    \
	///		 6R    15B
	///     /   \   /  \
	///    3B  8B 11R  18R
	///      \
	///      4R
	///  删除 8时 x的兄弟w是黑色的，且w的右孩子是红色的。
	/// <param name="node"></param>
	void deleteCaseFive(RedBlackNode* node);

	///		
	/// 		9B 
	///		  /    \
	///		 6R    15B
	///     /   \   /  \
	///    3B  8B 11R  18R
	///   /  \
	///  1R  4R
	/// 
	/// 删除9时 当前node指针指向了8B 8B的兄弟节点时黑色且左右孩子都是红色
	/// x的兄弟w是黑色的，且w的俩个孩子都是红色的
	void deleteCaseSix(RedBlackNode* node);


	/// <summary>
	/// 清理红黑树【只有一个根节点时】
	/// </summary>
	void clearByOnlyHaveOneNode();

public:
	RedBlackAbstruct();

	RedBlackAbstruct(int key, int value);

	RedBlackNode* getRoot() const;

	void setRoot(RedBlackNode* node);

	/// <summary>
	/// 查找节点
	/// </summary>
	/// <param name="key"></param>
	/// <returns></returns>
	RedBlackNode* findNode(int key);
	
};

